{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximize Total Tastiness of Purchased Fruits"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxTastiness"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大限度地提高购买水果的口味"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你有两个非负整数数组 <code>price</code> 和 <code>tastiness</code>，两个数组的长度都是 <code>n</code>。同时给你两个非负整数 <code>maxAmount</code> 和 <code>maxCoupons</code>。</p>\n",
    "\n",
    "<p data-group=\"1-1\">对于范围 <code>[0, n - 1]</code>&nbsp;中的每一个整数 <code>i</code>:</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>\n",
    "\t<p data-group=\"1-1\"><code>price[i]</code>&nbsp;描述了第 <code>i</code> 个水果的价格。</p>\n",
    "\t</li>\n",
    "\t<li><code>tastiness[i]</code> 描述了第 <code>i</code> 个水果的味道。</li>\n",
    "</ul>\n",
    "\n",
    "<p>你想购买一些水果，这样总的味道是最大的，总价不超过 <code>maxAmount</code>。</p>\n",
    "\n",
    "<p>此外，你还可以用优惠券以&nbsp;<strong>半价 </strong>购买水果 (向下取整到最接近的整数)。您最多可以使用 <code>maxCoupons</code>&nbsp;次该优惠券。</p>\n",
    "\n",
    "<p>返回可购买的最大总口味。</p>\n",
    "\n",
    "<p><strong>注意:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>每个水果最多只能购买一次。</li>\n",
    "\t<li>一个水果你最多只能用一次折价券。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> price = [10,20,20], tastiness = [5,8,8], maxAmount = 20, maxCoupons = 1\n",
    "<strong>输出:</strong> 13\n",
    "<strong>解释:</strong> 可以用以下方法来达到总口味:\n",
    "- 无优惠券买第一个水果，总价= 0 + 10，总口味= 0 + 5。\n",
    "- 用优惠券买第二个水果，总价= 10 + 10，总口味= 5 + 8。\n",
    "- 不购买第三个水果，总价= 20，总口味= 13。\n",
    "可以证明 13 是所能得到的最大总口味。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> price = [10,15,7], tastiness = [5,8,20], maxAmount = 10, maxCoupons = 2\n",
    "<strong>输出:</strong> 28\n",
    "<strong>解释:</strong> 可以用以下方法使总口味达到 20:\n",
    "- 不买第一个水果，这样总价= 0，总口味= 0。\n",
    "- 用优惠券买第二个水果，总价= 0 + 7，总口味= 0 + 8。\n",
    "- 用优惠券买第三个水果，总价= 7 + 3，总口味= 8 + 20。\n",
    "可以证明，28 是所能得到的最大总口味。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == price.length == tastiness.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 100</code></li>\n",
    "\t<li><code>0 &lt;= price[i], tastiness[i], maxAmount &lt;= 1000</code></li>\n",
    "\t<li><code>0 &lt;= maxCoupons &lt;= 5</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximize-total-tastiness-of-purchased-fruits](https://leetcode.cn/problems/maximize-total-tastiness-of-purchased-fruits/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximize-total-tastiness-of-purchased-fruits](https://leetcode.cn/problems/maximize-total-tastiness-of-purchased-fruits/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[10,20,20]\\n[5,8,8]\\n20\\n1', '[10,15,7]\\n[5,8,20]\\n10\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTastiness(self, price: List[int], tastiness: List[int], maxAmount: int, maxCoupons: int) -> int:\n",
    "        # dp[i][j]记录使用i张优惠券及j元钱时可以获得的最大甜度值，当记录为-math.inf时说明不存在这样的组合\n",
    "        dp = [[-math.inf] * (maxAmount + 1) for _ in range(maxCoupons + 1)]\n",
    "        # 一块钱也不花，一张券也不用时显然获得的甜度值为0\n",
    "        dp[0][0] = 0\n",
    "        # 遍历所有price, tastiness对\n",
    "        for p, t in zip(price, tastiness):\n",
    "            # 如果当前甜度值为0，那么花钱买该水果无意义\n",
    "            if t == 0:\n",
    "                continue\n",
    "\n",
    "            # 如果当前水果的半价都高于总金额，则显然无法买下当前水果\n",
    "            p_ = p >> 1\n",
    "            if p_ > maxAmount:\n",
    "                continue\n",
    "\n",
    "            # 用上一阶段dp值初始化下一阶段的dp值\n",
    "            tmp_dp = [dp[i].copy() for i in range(maxCoupons + 1)]\n",
    "\n",
    "            # 先考虑dp记录中已经用完了所有优惠券的情况，即dp的最后一行dp[maxCoupons]，或dp[-1]\n",
    "            # 遍历所有已经使用的金额j\n",
    "            for j in range(maxAmount + 1):\n",
    "                # 若当前状态不合法，跳过\n",
    "                if dp[-1][j] == -math.inf:\n",
    "                    continue\n",
    "                # 若已花金额加上当前水果金额超过了总金额，则后续的j也会让j+p超出总金额，可直接break\n",
    "                if j + p > maxAmount:\n",
    "                    break\n",
    "                # 用花费j元钱获得的最大甜度加上当前水果的甜度t，来更新花费j+p元可获得的最大甜度\n",
    "                tmp = dp[-1][j] + t\n",
    "                if tmp > tmp_dp[-1][j + p]:\n",
    "                    tmp_dp[-1][j + p] = tmp\n",
    "\n",
    "            # 当已用优惠券不到总优惠券数量时，可以考虑对当前水果再用一张代金券，此时遍历所有小于maxCoupons的i\n",
    "            for i in range(maxCoupons):\n",
    "                # 遍历所有已花费的金额j\n",
    "                for j in range(maxAmount + 1):\n",
    "                    # 若不存在已用i张优惠券且花费总金额为j的方案，则跳过\n",
    "                    if dp[i][j] == -math.inf:\n",
    "                        continue\n",
    "                    # 若已花金额加上当前水果的半价都超过了总金额，则在已花费金额大于j元的情况下，\n",
    "                    # 无论后续是否使用代金券都无法购入当前水果，故可break\n",
    "                    if j + p_ > maxAmount:\n",
    "                        break\n",
    "                    # 用已花i张优惠券和j元可获得的最大甜度加上当前水果的甜度来更新\n",
    "                    tmp = dp[i][j] + t\n",
    "                    # 若它比当前记录的多花一张优惠券且多花当前水果的半价获得的甜度大，则更新\n",
    "                    if tmp > tmp_dp[i + 1][j + p_]:\n",
    "                        tmp_dp[i + 1][j + p_] = tmp\n",
    "                    # 若j+p未超过总金额，则可在不花费额外优惠券的情况下购入当前水果\n",
    "                    if j + p <= maxAmount and tmp > tmp_dp[i][j + p]:\n",
    "                        tmp_dp[i][j + p] = tmp\n",
    "\n",
    "            dp = tmp_dp\n",
    "\n",
    "        return max(max(rec) for rec in dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # dfs\n",
    "    def maxTastiness(self, price: List[int], tastiness: List[int], maxAmount: int, maxCoupons: int) -> int:\n",
    "        n=len(price)\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(i, money, coupon):\n",
    "            if i == n:\n",
    "                return 0\n",
    "\n",
    "            res = 0\n",
    "            if money >= price[i]:\n",
    "                res = max(res, tastiness[i] + dfs(i+1, money - price[i], coupon))\n",
    "\n",
    "            if money >= price[i] // 2 and coupon > 0:\n",
    "                res = max(res, tastiness[i] + dfs(i+1, money - price[i] // 2, coupon - 1))\n",
    "\n",
    "            res = max(res, dfs(i+1, money, coupon))\n",
    "            return res\n",
    "\n",
    "\n",
    "        return dfs(0, maxAmount, maxCoupons)\n",
    "        \n",
    "\n",
    "# dp\n",
    "from copy import deepcopy\n",
    "\n",
    "class Solution:\n",
    "    def maxTastiness(self, price: List[int], tastiness: List[int], maxAmount: int, maxCoupons: int) -> int:\n",
    "        dp = [[0] * (maxAmount + 1) for _ in range(maxCoupons + 1)]\n",
    "        for p, t in zip(price, tastiness):\n",
    "            new_dp = deepcopy(dp)\n",
    "            for i in range(len(dp)):\n",
    "                for j in range(p, maxAmount + 1):\n",
    "                    new_dp[i][j - p] = max(new_dp[i][j - p], dp[i][j] + t)\n",
    "\n",
    "                if i < maxCoupons:\n",
    "                    half_p = p // 2\n",
    "                    for j in range(half_p, maxAmount + 1):\n",
    "                        new_dp[i][j - half_p] = max(new_dp[i][j - half_p], dp[i + 1][j] + t)\n",
    "\n",
    "            dp = deepcopy(new_dp)\n",
    "            \n",
    "        return max(max(row) for row in dp)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTastiness(self, price: List[int], tastiness: List[int], maxAmount: int, maxCoupons: int) -> int:\n",
    "        n = len(price)\n",
    "        price, tastiness = zip(*sorted(zip(price, tastiness)))\n",
    "        @cache\n",
    "        def f(i, k, mount):\n",
    "            if i == n: return 0\n",
    "            rnt = 0\n",
    "            if price[i] <= mount: \n",
    "                rnt = max(rnt, tastiness[i] + f(i+1, k, mount-price[i]))\n",
    "            if price[i] // 2 <= mount and k: \n",
    "                rnt = max(rnt, tastiness[i] + f(i+1, k-1, mount-price[i] // 2))\n",
    "            return max(rnt, f(i+1, k, mount))\n",
    "        ans = f(0, maxCoupons, maxAmount)\n",
    "        f.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTastiness(self, price: List[int], tastiness: List[int], maxAmount: int, maxCoupons: int) -> int:\n",
    "        n = len(price)\n",
    "        price, tastiness = zip(*sorted(zip(price, tastiness)))\n",
    "        print(price, tastiness)\n",
    "        @cache\n",
    "        def f(i, k, mount):\n",
    "            if i == n: return 0\n",
    "            rnt = 0\n",
    "            if price[i] <= mount: \n",
    "                rnt = max(rnt, tastiness[i] + f(i+1, k, mount-price[i]))\n",
    "            if price[i] // 2 <= mount and k: \n",
    "                rnt = max(rnt, tastiness[i] + f(i+1, k-1, mount-price[i] // 2))\n",
    "            return max(rnt, f(i+1, k, mount))\n",
    "        ans = f(0, maxCoupons, maxAmount)\n",
    "        f.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def maxTastiness(self, price: List[int], tastiness: List[int], maxAmount: int, maxCoupons: int) -> int:\n",
    "        n = len(price)\n",
    "        dp = [[[0] * (maxAmount + 1) for _ in range(maxCoupons + 1)] for _ in range(n + 1)]\n",
    "        \n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(maxCoupons + 1):\n",
    "                for k in range(maxAmount + 1):\n",
    "                    # 不购买第i个水果\n",
    "                    dp[i][j][k] = dp[i-1][j][k]\n",
    "                    # 购买第i个水果但不使用优惠券\n",
    "                    if k >= price[i-1]:\n",
    "                        dp[i][j][k] = max(dp[i][j][k], dp[i-1][j][k-price[i-1]] + tastiness[i-1])\n",
    "                    # 购买第i个水果并使用优惠券\n",
    "                    if j > 0 and k >= price[i-1]//2:\n",
    "                        dp[i][j][k] = max(dp[i][j][k], dp[i-1][j-1][k-price[i-1]//2] + tastiness[i-1])\n",
    "        \n",
    "        return dp[n][maxCoupons][maxAmount]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTastiness(self, price: List[int], tastiness: List[int], maxAmount: int, maxCoupons: int) -> int:\n",
    "        n = len(price)\n",
    "        dp = [[[0 for _ in range(maxCoupons + 1)] for _ in range(maxAmount + 1)] for _ in range(n)]\n",
    "        if price[0] <= maxAmount:\n",
    "           dp[0][price[0]][maxCoupons] = tastiness[0]\n",
    "        if maxCoupons >= 1 and price[0] // 2 <= maxAmount:\n",
    "            dp[0][price[0] // 2][maxCoupons - 1] = tastiness[0]\n",
    "    \n",
    "        for i in range(1,n):\n",
    "            for j in range(maxAmount + 1):\n",
    "                for k in range(maxCoupons + 1):\n",
    "                    dp[i][j][k] = max(dp[i][j][k],dp[i - 1][j][k])\n",
    "                    if k == 0:\n",
    "                        # 不能优惠\n",
    "                        if j + price[i] <= maxAmount:\n",
    "                            dp[i][j + price[i]][k] = max(dp[i][j + price[i]][k],dp[i - 1][j][k] + tastiness[i])\n",
    "                    else:\n",
    "                        # 不优惠\n",
    "                        if j + price[i] <= maxAmount:\n",
    "                            dp[i][j + price[i]][k] = max(dp[i][j + price[i]][k],dp[i - 1][j][k] + tastiness[i])\n",
    "\n",
    "                        # 优惠\n",
    "                        if j + price[i] // 2 <= maxAmount:\n",
    "                            dp[i][j + price[i] // 2][k - 1] = max(dp[i][j + price[i] // 2][k - 1],dp[i - 1][j][k] + tastiness[i])\n",
    "                            \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(maxAmount + 1):\n",
    "                ans = max(ans,dp[i][j][0])\n",
    "        return ans\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTastiness(self, price: List[int], tastiness: List[int], maxAmount: int, maxCoupons: int) -> int:\n",
    "        n = len(tastiness)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, rest, coupons):\n",
    "            if rest < 0 or coupons < 0:\n",
    "                return -inf \n",
    "            if i == n:\n",
    "                return 0            \n",
    "            res = max(dfs(i + 1, rest, coupons), dfs(i + 1, rest - price[i], coupons) + tastiness[i], dfs(i + 1, rest - price[i] // 2, coupons - 1) + tastiness[i])\n",
    "            return res \n",
    "        \n",
    "        ans = dfs(0, maxAmount, maxCoupons)\n",
    "        dfs.cache_clear()\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTastiness(self, price: List[int], tastiness: List[int], maxAmount: int, maxCoupons: int) -> int:\n",
    "        dp = dict()\n",
    "        dp[0,0,0] = 0\n",
    "\n",
    "        def maxTaste(idx, nc, amount):\n",
    "            if (idx, nc, amount) in dp:\n",
    "                return dp[idx, nc, amount]\n",
    "            elif (idx <= 0) or  (nc <0 )or (amount < 0):\n",
    "                return 0\n",
    "\n",
    "            t1, t2, t3 = 0, 0, 0\n",
    "            \n",
    "            p = price[idx - 1]\n",
    "            t = tastiness[idx - 1]\n",
    "            t1 = maxTaste(idx-1, nc, amount)\n",
    "            if amount >=p:\n",
    "                t2 = maxTaste(idx-1, nc, amount - p) + t\n",
    "            if nc>0 and amount>=p//2:\n",
    "                t3 = maxTaste(idx -1, nc-1, amount - p//2) + t\n",
    "\n",
    "            max_t = max(t1, t2, t3)\n",
    "            dp[idx, nc, amount] = max_t\n",
    "            return max_t\n",
    "        \n",
    "        return maxTaste(len(price), maxCoupons, maxAmount)\n",
    "        \n",
    "\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTastiness(self, price: List[int], tastiness: List[int], maxAmount: int, maxCoupons: int) -> int:\n",
    "        dp = dict()\n",
    "        # dp[0,0,0] = 0\n",
    "\n",
    "        def maxTaste(idx, nc, amount):\n",
    "            if (idx, nc, amount) in dp:\n",
    "                return dp[idx, nc, amount]\n",
    "            elif (idx <= 0) or  (nc <0 )or (amount < 0):\n",
    "                return 0\n",
    "\n",
    "            t1, t2, t3 = 0, 0, 0\n",
    "            \n",
    "            p = price[idx - 1]\n",
    "            t = tastiness[idx - 1]\n",
    "            t1 = maxTaste(idx-1, nc, amount)\n",
    "            if amount >=p:\n",
    "                t2 = maxTaste(idx-1, nc, amount - p) + t\n",
    "            if nc>0 and amount>=p//2:\n",
    "                t3 = maxTaste(idx -1, nc-1, amount - p//2) + t\n",
    "\n",
    "            max_t = max(t1, t2, t3)\n",
    "            dp[idx, nc, amount] = max_t\n",
    "            return max_t\n",
    "        \n",
    "        return maxTaste(len(price), maxCoupons, maxAmount)\n",
    "        \n",
    "\n",
    "            \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # dfs\n",
    "    def maxTastiness(self, price: List[int], tastiness: List[int], maxAmount: int, maxCoupons: int) -> int:\n",
    "        n=len(price)\n",
    "        @functools.lru_cache(None)\n",
    "        def dfs(i, money, coupon):\n",
    "            if i == n:\n",
    "                return 0\n",
    "\n",
    "            res = 0\n",
    "            if money >= price[i]:\n",
    "                res = max(res, tastiness[i] + dfs(i+1, money - price[i], coupon))\n",
    "\n",
    "            if money >= price[i] // 2 and coupon > 0:\n",
    "                res = max(res, tastiness[i] + dfs(i+1, money - price[i] // 2, coupon - 1))\n",
    "\n",
    "            res = max(res, dfs(i+1, money, coupon))\n",
    "            return res\n",
    "            \n",
    "\n",
    "        return dfs(0, maxAmount, maxCoupons)\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# -*- coding: utf-8 -*-\n",
    "from typing import List, Tuple, Optional\n",
    "from collections import deque, Counter\n",
    "from queue import PriorityQueue\n",
    "import math\n",
    "from functools import lru_cache\n",
    "# from sortedcontainers import SortedDict, SortedSet\n",
    "import random\n",
    "import copy\n",
    "import sys\n",
    "\n",
    "sys.setrecursionlimit(9999999)\n",
    "MOD = 10**9 + 7\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxTastiness(self, price: List[int], tastiness: List[int], maxAmount: int, maxCoupons: int) -> int:\n",
    "        n = len(price)\n",
    "\n",
    "        @lru_cache(typed=False, maxsize=1280000000)\n",
    "        def dp(ii, aa, bb):\n",
    "            if ii == n:\n",
    "                return 0\n",
    "\n",
    "            ans = dp(ii+1, aa, bb)\n",
    "            if aa >= price[ii]:\n",
    "                ans = max(ans, tastiness[ii] + dp(ii+1, aa-price[ii], bb))\n",
    "\n",
    "            if bb:\n",
    "                if aa >= price[ii] // 2:\n",
    "                    ans = max(ans, tastiness[ii] + dp(ii+1, aa-price[ii]//2, bb-1))\n",
    "\n",
    "            return ans\n",
    "\n",
    "        return dp(0, maxAmount, maxCoupons)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTastiness(self, price: List[int], tastiness: List[int], maxAmount: int, maxCoupons: int) -> int:\n",
    "        n=len(price)\n",
    "        @cache\n",
    "        def dfs(i,m,c):\n",
    "            if m<0 or c<0:return -100000000000\n",
    "            if i==n:return 0\n",
    "            p,t=price[i],tastiness[i]\n",
    "            return max(dfs(i+1,m,c),t+dfs(i+1,m-p,c),t+dfs(i+1,m-(p//2),c-1))\n",
    "        return dfs(0,maxAmount,maxCoupons)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxTastiness(self, price: List[int], tastiness: List[int], maxAmount: int, maxCoupons: int) -> int:\n",
    "        @cache\n",
    "        def dfs(i,m,c):\n",
    "            if m<0 or c<0:return -100000000000\n",
    "            if i==len(price):return 0\n",
    "            p,t=price[i],tastiness[i]\n",
    "            return max(dfs(i+1,m,c),t+dfs(i+1,m-p,c),t+dfs(i+1,m-(p//2),c-1))\n",
    "        return dfs(0,maxAmount,maxCoupons)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
